package com.test.daily.leetcode.y2022.m07.day0728.v04;

import java.util.*;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/28 下午 04:12
 * @version: 1.0
 */
public class Solution {
    public static class Node {
        public int in;
        public int out;
        public int value;
        public ArrayList<Node> nexts;
        public ArrayList<Edge> edges;

        public Node(int value) {
            this.value = value;
            this.in = 0;
            this.out = 0;
            this.edges = new ArrayList<>();
            this.nexts = new ArrayList<>();
        }

    }

    public static class Edge {
        public Node from;
        public Node to;
        public int weight;

        public Edge(Node from, Node to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    public static class Graph {
        HashMap<Integer, Node> nodes;
        HashSet<Edge> edges;

        public Graph() {
            this.nodes = new HashMap<>();
            this.edges = new HashSet<>();
        }
    }

    public static class UnionFind {
        public HashMap<Node, Integer> sizeMap;
        public HashMap<Node, Node> fatherMap;

        public UnionFind() {
            sizeMap = new HashMap<>();
            fatherMap = new HashMap<>();
        }

        public void makeSets(Collection<Node> nodes) {
            sizeMap.clear();
            fatherMap.clear();
            for(Node node: nodes){
                sizeMap.put(node, 1);
                fatherMap.put(node, node);
            }
        }
        public Node findFather(Node node){
            Stack<Node> path = new Stack<>();
            while(node != fatherMap.get(node)){
                path.push(node);
                node = fatherMap.get(node);
            }
            while(!path.isEmpty()){
                fatherMap.put(path.pop(), node);
            }
            return node;
        }
    }
}
